# coding: utf-8

'''
@autor1: João Batista nº5479
@autor2: Luis Cabaço nº5606
@data Inicio: 28/05/2013
@data Fim: 11/06/2013
'''

import math

class Algoritmos:
    '''
        Class Algoritmos:
            Esta class contem diversos algoritmos de organização. 
            A estrutura de dados utilizada em cada um dos algoritmos é o Array.
    '''

    def quick_sort(self, lista, inicio, fim):
        ''' 
            Quick Sort:
                Este algoritmo divide a lista ao meio através de um piloto. A lista é entao
                ordenada de forma a que todos os elementos à esquerda do piloto sejam inferiores
                a este, e à direita sejam superiores. Posteriormente as sublistas iram ser 
                ordenadas recursivamente à esquerda e à direita dos novos pilotos.

            Args:
                lista: lista de numeros a ordenar
                inicio: posição a partir da qual se quer ordenar a lista
                fim: posição a partir da qual se quer deixar de ordenar a lista

            Return:
                lista: Lista ordenada
        '''
        if inicio < fim:
            particao = self.__partition(lista, inicio, fim)
            self.quick_sort(lista, inicio, particao - 1 )
            self.quick_sort(lista, particao + 1, fim)
            pass

        return lista

    
    
    def __partition(self, lista, inicio, fim):
        '''
            Este método privado é chamado pelo Quick Sort
        '''
        valorUltimoElemento = lista[fim]
        posicaoInicial = inicio - 1

        #por cada elemento da partição, compara os elementos e troca as suas posições       
        for elemento in xrange(inicio, fim):
            if lista[elemento] <= valorUltimoElemento:
                posicaoInicial += 1
                lista[posicaoInicial], lista[elemento] = lista[elemento], lista[posicaoInicial]
                pass
            else:
                #não faz nada
                pass
            pass

        lista[posicaoInicial + 1], lista[fim] = lista[fim], lista[posicaoInicial + 1]

        return posicaoInicial + 1
    
    
    def insertion_sort(self, lista):
        '''
            Insertion Sort:
                Este algoritmo é ideal para ordenar listas de pequenas dimensões. Comecando na
                primeira posicao, esse valor vai ser comparado com o anterior, e no caso de ser
                inferior troca até que a lista esteja toda organizada à esquerda da posição. Quando estiver
                a posição é incrementada e repete o processo até chegar à ultima posição da lista.


            Args:
                lista: lista de numeros a ordenar
                
            Return:
                lista: Lista ordenada
        '''

        tamanhoLista = len(lista)

        #selecciona um elemento da lista e recua uma posição
        for elemento in xrange(1, tamanhoLista):
            chave = lista[elemento]
            valor = elemento - 1

            #compara enquanto a chave for menor que o valor e 
            #quando for maior troca os elementos
            while(valor >= 0 and lista[valor] > chave):
                lista[valor+1] = lista[valor]
                valor -= 1
                pass

            lista[valor+1] = chave
            pass

        return lista

    def merge_sort(self, lista):
        '''
            Merge Sort:
                Este algoritmo divide a lista em sub-listas até que os elementos estejam todos separados.
                Posteriormente vai ordenando e juntando novamente em listas cada vez maiores até ter uma 
                lista completa e ordenada.

            Args:
                lista: lista de numeros a ordenar
                inicio: posição a partir da qual se quer ordenar a lista
                fim: posição a partir da qual se quer deixar de ordenar a lista

            Return:
                resultado: Lista ordenada
        '''
        if len(lista) <= 1:
            return lista
        
        #cria duas listas separadas pela metade a partir da original
        meio = len(lista) / 2
        esquerda = self.merge_sort(lista[:meio])
        direita = self.merge_sort(lista[meio:])

        resultado = []

        #enquanto as listas tiverem valores
        while len(esquerda) > 0 and len(direita) > 0:
            # se o valor da esquerda for superior ao da direita
            # adiciona o valor da direita ao resultado 
            if esquerda[0] > direita[0]:   
                resultado.append(direita.pop(0))
            else:
                resultado.append(esquerda.pop(0))
        
        #adiciona os valores restantes ao resultado
        if len(esquerda) > 0:
            resultado.extend(self.merge_sort(esquerda))
        else:
            resultado.extend(self.merge_sort(direita))

        return resultado

    def bubble_sort(self, lista):
        '''
            Bubble Sort:
                Este algoritmo verifica o primeiro e segundo valor, e coloca o menor a esquerda
                e o maior a direita. Depois de ordenados incrementa uma posição em ambos. Este processo
                é repetido até ao final da lista. Isto volta a repetir-se até que a lista esteja ordenada.

            Args:
                lista: lista de numeros a ordenar

            Return:
                lista: Lista ordenada
        '''

        tamanhoLista = len(lista)

        #enquanto a lista não estiver oredenada
        while(tamanhoLista != 0):
            novoElemento = 0

            #verifica cada par de elementos adjacentes
            for elemento in xrange(1, tamanhoLista):
                if (lista[elemento - 1] > lista[elemento]):
                    lista[elemento - 1], lista[elemento] = lista[elemento], lista[elemento - 1]
                    novoElemento = elemento
                    pass
                pass

            tamanhoLista = novoElemento

            pass

        return lista

    def heap_sort(self, lista):
        '''
            Heap Sort:
                Este algoritmo organiza a lista numa Heap com inicio no valor maximo.
                Posteriormente vai ser retirado o maior valor da heap e inserido no array,
                seguido pela reconstrução da Heap. Quando a Heap estiver vazia significa que
                o array está ordenado.

            Args:
                lista: lista de numeros a ordenar

            Return:
                lista: Lista ordenada
        '''
        self.__heapify(lista) # ordena a lista em max-heap

        tamanhoLista = len(lista) - 1

        while (tamanhoLista > 0):
            lista[tamanhoLista], lista[0] = lista[0], lista[tamanhoLista]
            tamanhoLista -= 1
            self.__shiftDown(lista, 0, tamanhoLista)
            pass

        return lista

    def __heapify(self, lista):
        '''
            Este método privado é chamado pelo Heap Sort
            O método cria uma heap ordenada 
        '''
        inicio = (len(lista)-1) / 2

        while (inicio >= 0):
            self.__shiftDown(lista, inicio, len(lista)-1)
            inicio -= 1
            pass
        pass

    def __shiftDown(self, lista, inicio, tamanhoLista):
        '''
            Este método privado é chamado pelo Heapify
        '''
        raiz = inicio

        while (raiz * 2 + 1 <= tamanhoLista):
            filho = raiz * 2 + 1
            troca = raiz

            if lista[troca] < lista[filho]:
                troca = filho
                pass

            if filho + 1 <= tamanhoLista and lista[troca] < lista[filho+1]:
                troca = filho + 1
                pass

            if troca != raiz:
                lista[raiz], lista[troca] = lista[troca], lista[raiz]
                raiz = troca
                pass

            else:
                return

    def shell_sort(self, lista):
        '''
            Shell Sort:
                Este algoritmo utiliza a sequencia de gaps de Marcin Ciura.
                O Shell Sort utiliza o Insertion Sort entre os gaps para ordenar a lista
                de uma maneira mais eficiente que o proprio Insertion Sort na totalidade
                da lista.

            Args:
                lista: lista de numeros a ordenar

            Return:
                lista: Lista ordenada
        '''
        #Sequencia de gaps de Marcin Ciura
        gaps = [701, 301, 132, 57, 23, 10, 4, 1]

        #ciclo para percorrer cada um dos gaps
        for gap in gaps:
            
            #ciclo para verificar os valores com uma distancia "gap"
            #ate ao final da lista
            for elemento in xrange(gap, len(lista)):

                temp = lista[elemento]
                posicao = elemento

                #enquanto os valores estiverem trocados
                while( posicao >= gap and lista[posicao - gap] > temp):
                    lista[posicao] = lista[posicao - gap]
                    posicao -= gap
                    pass

                lista[posicao] = temp
                pass
            pass

        return lista

    def selection_sort(self, lista):
        '''
            Selection Sort:
                Este algoritmo percorre a lista e vai trocando o menor valor para a primeira 
                posicao da lista. Uma vez trocado, essa posição aumenta e volta a procurar o
                menor valor seguinte no resto da lista, e assim sucessivamente.

            Args:
                lista: lista de numeros a ordenar
                inicio: posição a partir da qual se quer ordenar a lista
                fim: posição a partir da qual se quer deixar de ordenar a lista

            Return:
                lista: Lista ordenada
        '''

        tamanhoLista = len(lista)

        #posição a ser alterada
        for elemento in xrange(0,tamanhoLista):

            chave = elemento

            #posição do elemento para comparar
            for piloto in xrange(elemento + 1, tamanhoLista):

                if(lista[piloto] < lista[chave]):
                    chave = piloto
                    pass
                pass
            pass

            if (chave != elemento):
                lista[elemento], lista[chave] = lista[chave], lista[elemento]
                pass
            pass
        
        return lista
    
    def bucket_sort(self, lista):
        '''
            Bucket Sort:
                O algoritmo cria um array de arrays(baldes) e divide os elementos do
                array a ordenar pelos baldes correspondentes.
                Posteriormente, utilizando o insertion_sort, ordena os baldes que tem elementos.
                Finalmente adiciona os baldes, por ordem, à lista ordenada.

            Args:
                lista: lista de numeros a ordenar

            Return:
                listaOrdenada: Lista ordenada
        '''
        baldes = [] # array de arrays
        maiorValor = 0
        
        #descobrir o maior valor na lista
        for x in xrange(0,len(lista)):
            if (lista[x] > maiorValor):
                maiorValor = lista[x]
                pass
            pass

        #descobrir o numero de baldes e a capacidade em cada balde
        elementosInBalde = 1000

        nrDeBaldes = int(math.floor(maiorValor / elementosInBalde) + 1)

        #criar a lista de baldes vazios
        for x in xrange(0, nrDeBaldes):
            baldes.append([])
            pass

        valorMinimo = 0
        valorMaximo = elementosInBalde - 1

        # adiciona os valores ao balde correspondente
        for balde in baldes:
            for valor in lista:
                if (valorMinimo <= valor <= valorMaximo):
                    balde.append(valor)
                    pass
                pass
            valorMinimo += elementosInBalde
            valorMaximo += elementosInBalde
            pass

        # ordenda cada balde
        for balde in baldes:
            if(len(balde) != 0):
                self.insertion_sort(balde)
            pass

        #adiciona os valores dos balde a lista ordenada
        listaOrdenada = []

        for balde in baldes:
            listaOrdenada.extend(balde)
            pass

        return listaOrdenada

    pass # Fim da class Algoritmos